package test230531;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/31 16:40
 * 740. 删除并获得点数
 * https://leetcode.cn/problems/delete-and-earn/
 */
public class Solution04 {

    public int deleteAndEarn(int[] nums) {
        // 如果数组nums值是连续且递增的, 那么就是一个打家劫舍的问题
        // 使用 count 数组进行存储, count[i]存储 nums 中 i 对应的点数, 由于count数组的index连续, 可以转化成打家劫舍问题
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        int[] count = new int[max + 1];
        for (int num : nums) {
            count[num] += num;
        }
        int res = ransackHomesAndHouses(count);
        return res;
    }

    // 打家劫舍问题处理
    public int ransackHomesAndHouses(int[] nums) {
        // f[i] 表示 i 位置偷的最大点数
        // g[i] 表示 i 位置不偷的最大点数
        int[] f = new int[nums.length];
        int[] g = new int[nums.length];
        f[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1], f[i - 1]);
        }
        return Math.max(f[nums.length - 1], g[nums.length - 1]);
    }
}
